
import java.util.Stack;

/**
 * created by lpw
 */
public class TestClass {
    public static void main(String[] args) {
        Node node = createLinked(10);
//        logNode(node);
        Node node1 = linkedReversal2(node);
        logNode(node1);
    }

    //打印链表
    public static void logNode(Node node){
        Node temp=node;
        while (temp!=null){
            System.out.println(temp.data);
            temp=temp.next;
        }
    }

    //生成链表
    public static Node createLinked(int len){
        Node node=new Node();
        Node tempNode=node;
        for (int i = 0; i < len; i++) {
            char c=(char)(65+i);
            tempNode.data=String.valueOf(c);
            if (i!=len-1){
                tempNode.next=new Node();
                tempNode=tempNode.next;
            }
        }
        return node;
    }

    //使用栈来反转链表，
    public static Node linkedReversal2(Node oldNode){
        if (oldNode==null)return null;
        Stack<Node> stack=new Stack();
        Node temp=oldNode;
        //都入栈
        while (temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        //出栈
        Node head=stack.pop();
        temp=head;
        while (!stack.empty()){
            temp.next=stack.pop();
            temp=temp.next;
        }
        //把最后一个下一个节点置空
        temp.next=null;
        return head;
    }

    //使用遍历反转链表
    public static Node linkedReversal(Node oldNode){
        if (oldNode == null) return null;
        Node pre = oldNode;
        Node cur = oldNode.next;
        Node temp;
        while (cur != null) {// 为空，说明到最后了
            temp = cur.next;
            cur.next=pre;// 反转指针域的指向
            // 指针往下移动
            pre = cur;
            cur = temp;
        }
        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
        oldNode.next=null;
        return pre;
    }
}

class Node {
    String data;
    Node next;
}